s = "leetcode"
wordDict = ["leet", "code"]

n = len(s)
maxWord = 0
dp = [False] * (n + 1)
for word in wordDict:
    maxWord = max(maxWord, len(word))
dp[0] = True
for i in range(1, n + 1):
    for j in range(1, maxWord + 1):
        left = max(0, i - j)
        dp[i] |= (s[left:i] in wordDict) and dp[left]

print(dp[n])
